/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.left = (left === undefined ? null : left)
        this.right = (right === undefined ? null : right)
    }
}

// function maxPathSum(root: TreeNode | null): number {
//     // dp[i]: max(from curRoot down to leaf)
    
    
    
//     // 0: left or right
//     // 1: curRoot + left or right
//     // 2: curRoot + left + right
//     // 3: curRoot
// }

class MaxVal {
    val: number
    constructor(val: number) {
        this.val = val
    }
}

function maxPathSum_inner(root: TreeNode | null, max_val_obj: MaxVal): number {
    if (root === null) {
        return 0;
    }
    let leftDownMax = maxPathSum_inner(root.left, max_val_obj);
    let rightDownMax = maxPathSum_inner(root.right, max_val_obj);

    /* only update max_val_obj by all paths includes curRoot(root.val) */

    // 1: max(curRoot down to leaf)
    // 1-1: curRoot + left or right
    // 1-2: curRoot 
    const curRootDownMax = root.val + Math.max(leftDownMax, rightDownMax, 0);
    max_val_obj.val = Math.max(max_val_obj.val, curRootDownMax);
    // 2: curRoot + left + right
    max_val_obj.val = Math.max(max_val_obj.val, root.val + leftDownMax + rightDownMax);

    return curRootDownMax;
}

function maxPathSum(root: TreeNode | null): number {
    let maxVal = new MaxVal(Number.MIN_SAFE_INTEGER);
    maxPathSum_inner(root, maxVal);
    return maxVal.val;
}

// input_cases = [[1,2,3]]
